class Solution {
public:
    int rob(vector<int>& nums) {

        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
        vector<int> flags(nums.size() + 1, 0);
        vector<int> value(nums.size() + 1, 0);

        value[1] = nums[0];
        flag[1] = 1;

        value[2] = nums[0] > nums[1] ? nums[0] : nums[1];
        flag[2] = nums[0] > nums[1] ? 0 : 1;

        for(int i = 2; i < nums.size(); i++){
          value[i + 1] = value[i - 2];
          value[i + 1] = value[i - 1] > value[i + 1] ? value[i - 1] : value[i + 1];
          value[i + 1] = value[i] > value[i + 1] ? value[i] : value[i + 1];
          if(value[i - 2] + nums[i] > value[i + 1]){
            value[i + 1] = value[i - 2] + nums[i];
            flag[i+1] = 1;
          }
          if(value[i - 1] + nums[i] > value[i + 1]){
            value[i + 1] = value[i - 1] + nums[i];
            flag[i+1] = 1;
          }
          if(flag[i] == 0 && value[i] + nums[i] > value[i + 1]){
            value[i + 1] = value[i] + nums[i];
            flag[i+1] = 1;
          }
        }

        return value[nums.size() + 1];
    }
};
